package Stack;

import org.junit.Test;

import java.util.*;

/**
 * @BelongsProject: SeniorArchitect-LeetCode
 * @BelongsPackage: Stack
 * @Author: zhuangxiaoyan
 * @CreateTime: 2023-10-21  10:20
 * @Description: TODO
 * @Version: 1.0
 */
public class 下一个更大的元素496 {

    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        Deque<Integer> stack = new ArrayDeque<Integer>();
        for (int i = nums2.length - 1; i >= 0; --i) {
            int num = nums2[i];
            // 当前的值大于栈顶元素的值 栈顶的元素弹出 这压根栈是始终是的最大的元素
            while (!stack.isEmpty() && num >= stack.peek()) {
                stack.pop();
            }
            map.put(num, stack.isEmpty() ? -1 : stack.peek());
            stack.push(num);
        }
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; ++i) {
            res[i] = map.get(nums1[i]);
        }
        return res;
    }

    // 先求解对应的数组的单调栈的结果，然后在使用Hashmap来实现
    public int[] nextGreaterElement2(int[] nums1, int[] nums2) {
        int[] ans=new int[nums2.length];
        Arrays.fill(ans,-1);
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i <ans.length; i++) {
            while (!stack.isEmpty()&&nums2[i]>nums2[stack.peek()]){
                int index=stack.poll();
                ans[index]=nums2[i];
            }
            stack.push(i);
        }
        System.out.println(Arrays.toString(ans));
        HashMap<Integer,Integer> map=new HashMap<>();
        for (int i=0;i<ans.length;i++){
            map.put(nums2[i],ans[i]);
        }
        int[] result=new int[nums1.length];
        for (int i=0;i<nums1.length;i++){
            result[i]=map.get(nums1[i]);
        }
        return result;
    }

    @Test
    public void test(){
        int[] ints = nextGreaterElement2(new int[]{137,59,247},new int[]{137,59,247});
        System.out.println(Arrays.toString(ints));
    }
}
